package com.jojo.intermediate.day5_array;

import java.util.Arrays;

/**
 * 238、除自身以外数组的乘积
 *
 * 给你一个整数数组nums，返回数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。
 * 题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。
 *
 * 请不要使用除法，且在O(n) 时间复杂度内完成此题
 *
 * 示例 1:
 *
 * 输入: nums = [1,2,3,4]
 * 输出: [24,12,8,6]
 * 示例 2:
 *
 * 输入: nums = [-1,1,0,-3,3]
 * 输出: [0,0,9,0,0]
 */
public class ArrayProduct {

    /** myCode 保存左右乘积 */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        //左边所有数的乘积
        int[] leftPro = new int[n];
        leftPro[0] = 1;
        //右边所有数的乘积
        int[] rightPro = new int[n];
        rightPro[n - 1] = 1;
        for (int i = 1;i < n;i++){
            leftPro[i] = leftPro[i - 1] * nums[i - 1];
        }
        for (int i = n - 2;i >= 0;i--){
            rightPro[i] = rightPro[i + 1] * nums[i + 1];
        }
        for (int i = 0;i < n;i++){
            nums[i] = leftPro[i] * rightPro[i];
        }
        return nums;
    }

    /** myCode 保存左右乘积 */
    public int[] productExceptSelf2(int[] nums) {
        int n = nums.length;
        //结果数组
        int[] result = new int[n];
        result[0] = 1;
        int rightPro = 1;
        for (int i = 1;i < n;i++){
            result[i] = result[i - 1] * nums[i - 1];
        }
        for (int i = n - 1;i >= 0;i--){
            result[i] = result[i] * rightPro;
            rightPro = rightPro * nums[i];
        }
        return result;
    }

    public static void main(String[] args) {
        ArrayProduct pro = new ArrayProduct();
        int[] arr = {1,2,3,4};
        int[] ints = pro.productExceptSelf2(arr);
        System.out.println(Arrays.toString(ints));
    }
}
